// Copyright (c) 2009 Jonathan Traugott & Christopher Keith (chris.keith@gmail.com)
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following
// conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.

// Implement ordered link list

#include <iostream>
#include <assert.h>
using namespace std;

struct node {
	int info;
	node * link;
};

node * createNode(int val) { // create a node with this value for info
	node*	ret = new node;
	ret->info = val;
	ret->link = NULL;
	return ret;
}

node*	findPredecessorNode(node * first, int val) {
	while (first->link != NULL) {
		if (first->link->info >= val) {
			break;
		}
		first = first->link;
	}
	return first;
}

void insertVal(node * first, int val) { // insert val in order
	node*	p = findPredecessorNode(first, val);
	node*	n = createNode(val);
	n->link = p->link;
	p->link = n;
}

node* deleteSuccessorNode(node* p) {
	if (p->link != NULL) {
		node*	t = p->link;
		p->link = p->link->link;
		delete t;
	}
	return p;
}

void deleteVal(node * first, int val) {  // delete the first node with this value
	node*	p = findPredecessorNode(first, val);
	deleteSuccessorNode(p);
}

void deleteRange(node * first, int min, int max) {
// delete all nodes whose info is in [min,max]. Do this efficiently.
	assert(min <= max);
	node*	p = findPredecessorNode(first, min);
	while ((p->link != NULL) && (p->link->info <= max)) {
		p = deleteSuccessorNode(p);
	}
}

void clearList(node * first) { // clear the list
	while (first != NULL) {
		node*	t = first;
		first = first->link;
		delete t;
	}
}

void clear(node * dummy) {
	clearList(dummy->link);
	dummy->link = NULL;
}

void print(node * first) { // print the list
	if (first == NULL) {
		cout << "empty list!" << endl;
	} else {
		int		i = 0;
		while (first != NULL) {
			cout << i << "\t" << first->info << endl;
			i++;
			first = first->link;
		}
	}
}

void recursivePrint(node * n, int pI) {
	if (n->link != NULL) {
		recursivePrint(n->link, pI+1);
	}
	cout << /* * */ pI << "\t" << n->info << endl;
}

void reversePrint(node * first) { // print the list backwards
	if (first->link == NULL) {
		cout << "empty list!" << endl;
	} else {
		int		i = 0;
		recursivePrint(first->link, /* & */ i);
	}
}

node * copy(node * first) { // return a copy of the list
	node*	ret = new node;
	ret->link = NULL;
	node*	n = ret;
	while (first->link != NULL) {
		n->link = createNode(first->link->info);
		n = n->link;
		first = first->link;
	}
	return ret;
}

void insertAfter(node* f, int v) {
	node* t = createNode(v);
	t->link = f->link;
	f->link = t;
}

void merge(node * first, node * second) {
// merge the values in second with first. Leave second unchanged.
	while (second->link != NULL) {
		if (first->link == NULL) {
			insertAfter(first, second->link->info);
			second = second->link;
		} else if (second->link->info < first->link->info) {
			insertAfter(first, second->link->info);
			second = second->link;
		}
		first = first->link;
	}
}

class Tester {
public:
            Tester();
    void    Run();
	void	AutoTest();
private:
    node*	listA;
	node*	listB;

    char    GetCmd();
	void	Print();
	void	ReversePrint();
};

char    Tester::GetCmd() {
	cout << "Testing ordered linked list:" << endl;
    cout << "c: clear first list" << endl;
    cout << "d: delete in first list" << endl;
    cout << "D: delete range in first list" << endl;
    cout << "i: insert in first list" << endl;
    cout << "I: insert in second list" << endl;
    cout << "m: merge copy of second into first" << endl;
    cout << "p: print both lists" << endl;
    cout << "r: reverse print both lists" << endl;
    cout << "q: quit" << endl;
    char    cmd;
    cin >> cmd;
    return cmd;
}

void Tester::Print() {
	cout << "first list: " << endl;
	print(listA->link);
	cout << endl;
	cout << "second list: " << endl;
	print(listB->link);
	cout << endl;
}

void Tester::ReversePrint() {
cout << "first list: " << endl; reversePrint(listA); cout << endl;
				cout << "second list: " << endl; reversePrint(listB); cout << endl;
}

void Tester::Run() {
    char    cmd;
    while ( (cmd = GetCmd()) != 'q') {
		int		f;
		int		s;
        switch (cmd) {
			case 'c' : { clear(listA); break; }
			case 'd' : { cin >> f; deleteVal(listA, f); break; }
			case 'D' : { cin >> f >> s; deleteRange(listA, f, s); break; }
			case 'i' : { cin >> f; insertVal(listA, f); break; }
			case 'I' : { cin >> f; insertVal(listB, f); break; }
			case 'm' : { merge(listA, listB); break; }
			case 'p' : { Print(); break; }
			case 'r' : { ReversePrint(); break; }
            default: cout << "Unknown command: " << cmd << endl;    break;
        }
    }
}

Tester::Tester() {
    listA = createNode(-9999999);
	listB = createNode(-9999999);
}

void Tester::AutoTest() {
	insertVal(listA, 4);
	insertVal(listA, 6);
	insertVal(listB, 5);
	insertVal(listB, 7);
	Print();
	ReversePrint();
	merge(listA, listB);
	cout << "Testing merge:" << endl;
	Print();
	insertVal(listA, 1);
	insertVal(listA, 2);
	insertVal(listA, 2);
	insertVal(listA, 2);
	insertVal(listA, 3);
	Print();
	ReversePrint();
	cout << "Testing deleteRange(5,5):" << endl;
	deleteRange(listA, 5, 5);
	Print();
	cout << "Testing deleteRange(7, 8):" << endl;
	deleteRange(listA, 7, 8);
	Print();
	cout << "Testing deleteRange(8, 8):" << endl;
	deleteRange(listA, 8, 8);
	Print();
	cout << "Testing deleteRange(0,0):" << endl;
	deleteRange(listA, 0,0);
	Print();
	cout << "Testing deleteRange(2,3):" << endl;
	deleteRange(listA, 2, 3);
	Print();
	clear(listA);
	clear(listB);
}

int main() {
    Tester  t;
	t.AutoTest();
    t.Run();
}
